package com.sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @BelongsProject: DataStructures
 * @BelongsPackage: com.sort
 * @Author: 江岸
 * @CreateTime: 2021-02-02 23:21
 * @Description: 希尔排序 先分组，再插入
 */
public class ShellSort {

    public static void main(String[] args){
//        int[] arr = {5,42,78,11,37,894,131,-1,68,1134,-7,143,-666};
//        System.out.println(Arrays.toString(arr));
        int[] arr = new int[8000000];
        for (int i=0;i<arr.length;i++){
            arr[i] = (int) (Math.random()*80000000);
        }
        long l = System.currentTimeMillis();
        //先分组
        for (int gap=arr.length/2;gap>0;gap/=2 ){
            //再对每一组插入排序
            for(int i = gap;i<arr.length;i++){
                int insertIndex = i-gap;
                int insertValue = arr[i];
                while (insertIndex>=0 && insertValue<arr[insertIndex]){
                    arr[insertIndex+gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                arr[insertIndex+gap] = insertValue;
            }
        }
//        System.out.println(Arrays.toString(arr));
        long l1 = System.currentTimeMillis();
        System.out.println((l1-l));
    }
}
